`:top
In `F33f`_`[computer science`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_science]`_`f, a `!graph-structured stack`! (GSS) is a `F33f`_`[directed acyclic graph`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Directed_acyclic_graph]`_`f where each directed `F33f`_`[path`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Path_(graph_theory)]`_`f represents a `F33f`_`[stack`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Stack_(data_structure)]`_`f. The graph-structured stack is an essential part of `F33f`_`[Tomita's algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=GLR_parser]`_`f, where it replaces the usual `F33f`_`[stack`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Stack_(data_structure)]`_`f of a `F33f`_`[pushdown automaton`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Pushdown_automaton]`_`f. This allows the algorithm to encode the nondeterministic choices in parsing an `F33f`_`[ambiguous grammar`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Ambiguous_grammar]`_`f, sometimes with greater efficiency.
In the following diagram, there are four stacks: {7,3,1,0}, {7,4,1,0}, {7,5,2,0}, and {8,6,2,0}.
Another way to simulate nondeterminism would be to duplicate the stack as needed. The duplication would be less efficient since vertices would not be shared. For this example, 16 vertices would be needed instead of 9.
>>Contents
• `F0af`_`[Operations`#operations]`_`f
• `F0af`_`[References`#references]`_`f
-─
>>Operations
`B100`F9d9GSSnode* GSS::add(GSSnode* prev, int elem)`f`b
`B100`F9d9{`f`b
`B100`F9d9 int prevlevel = prev->level;`f`b
`B100`F9d9 assert(levels.size() >= prevlevel + 1);`f`b
`B100`F9d9 int level = prevlevel + 1;`f`b
`B100`F9d9 if (levels.size() == level)`f`b
`B100`F9d9 {`f`b
`B100`F9d9 levels.resize(level + 1);`f`b
`B100`F9d9 }`f`b
`B100`F9d9 GSSnode* node = findElemAtLevel(level, elem);`f`b
`B100`F9d9 if (node == nullptr)`f`b
`B100`F9d9 {`f`b
`B100`F9d9 node = new GSSnode();`f`b
`B100`F9d9 node->elem = elem;`f`b
`B100`F9d9 node->level = level;`f`b
`B100`F9d9 levels[level].push_back(node);`f`b
`B100`F9d9 }`f`b
`B100`F9d9 node->add(prev);`f`b
`B100`F9d9 return node;`f`b
`B100`F9d9}`f`b
`B100`F9d9void GSS::remove(GSSnode* node)`f`b
`B100`F9d9{`f`b
`B100`F9d9 if (levels.size() > node->level + 1)`f`b
`B100`F9d9 if (findPrevAtLevel(node->level + 1, node)) throw Exception("Can remove only from top.");`f`b
`B100`F9d9 for (int i = 0; i < levels[node->level].size(); i++)`f`b
`B100`F9d9 if (levels[node->level][i] == node)`f`b
`B100`F9d9 {`f`b
`B100`F9d9 levels[node->level].erase(levels[node->level].begin() + i);`f`b
`B100`F9d9 break;`f`b
`B100`F9d9 }`f`b
`B100`F9d9 delete node;`f`b
`B100`F9d9}`f`b
>>References
• Masaru Tomita. `*Graph-Structured Stack And Natural Language Parsing`*. Annual Meeting of the Association of Computational Linguistics, 1988. [1]
• Elizabeth Scott, Adrian Johnstone `*GLL Parsing`* gll.pdf
`c`F0af`_`[↑ Back to top`#top]`_`f`a